8356. Скидки

В супермаркете проводится акция – “Покупая два любых товара, третий получаешь бесплатно, из трех выбранных вами товаров оплачиваются два наиболее дорогих”.

Мамед, идя в супермаркет, знает, какие товары он хочет купить, и знает их стоимость. Определите минимальную сумму денег, которую ему нужно взять с собой, чтобы купить эти товары.

Вход. В первой строке задается одно число n (1 ≤ n ≤ 1000), а во второй строке n чисел – стоимости выбранных Мамедом товаров. Все стоимости – натуральные числа, не превышающие 10000.

Выход. Выведите одно число – минимальную сумму денег, которую Мамед должен взять с собой в супермаркет.

Примечание. Мамед сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок.

Пример входа	Пример выхода
6 1 5 4 3 5 7	19

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Отсортируем стоимости товаров. Далее движемся по массиву справа налево, обрабатываем товары по три: платим деньги за два наиболее дорогих товара и третий получаем бесплатно.

Пример

Отсортируем стоимости товаров.

Искомая наименьшая сумма равна 7 + 5 + 4 + 3 = 19.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Сортируем стоимости товаров.

sort(v.begin(), v.end());

В переменной res подсчитывем искомую наименьшую сумму денег. Стартуем с конца массива i = n – 1. Двигаемя влево тройками (i = i – 3). Для каждой тройки товаров с индеками i, i – 1, i – 2 оплачиваем два наиболее дорогих.

res = 0;

for (i = n - 1; i >= 0; i -= 3)

{

res += v[i];

if (i > 0) res += v[i - 1];

}

Выводим ответ.

printf("%d\n", res);